﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
// 原题连接：https://leetcode.cn/problems/score-of-parentheses/
/*
题目描述：
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
 

示例 1：
输入： "()"
输出： 1

示例 2：
输入： "(())"
输出： 2

示例 3：
输入： "()()"
输出： 2

示例 4：
输入： "(()(()))"
输出： 6
 

提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
*/

// 开始解题：
// 方法1——分治

int scoreOfParentheses(char* s) {
    int len = strlen(s);
    if (2 == len) {
        return 1;
    }
    int balance = 0;
    char* cur = s;
    int n = 0;
    while (*cur != '\0') {
        balance += *cur == '(' ? 1 : -1;
        n++;
        if (0 == balance) {
            break;
        }
        cur++;
    }
    if (n == len) {
        char* str = (char*)malloc((n - 1) * sizeof(char));
        if (NULL == str) {
            perror("malloc fail!\n");
            exit(-1);
        }
        str[n - 2] = '\0';
        strncpy(str, s + 1, n - 2);
        return 2 * scoreOfParentheses(str);
    }
    else {
        char* str1 = (char*)malloc((n + 1) * sizeof(char));
        if (NULL == str1) {
            perror("malloc fail!\n");
            exit(-1);
        }
        str1[n] = '\0';
        strncpy(str1, s, n);
        char* str2 = (char*)malloc((len - n + 1) * sizeof(char));
        if (NULL == str2) {
            perror("malloc fail!\n");
            exit(-1);
        }
        str2[len - n] = '\0';
        strncpy(str2, s + n, len - n);
        return scoreOfParentheses(str1) + scoreOfParentheses(str2);
    }
}

int main() {
	char str[] = "(()(()))";
	printf("%d\n", scoreOfParentheses(str));
	return 0;
}